package everyday;

/**
 * @author zhangmin
 * @create 2022-04-25 10:21
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 *
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 * 思路：
 * 下一个排序一定是要将一个小数与他后面的一个大数交换，
 * 从后向前找到第一个下降的数，这个数就是需要交换到后面的小数，然后在这个数后面，从后向前找到第一个比这个小数大的数，这就是要交换的大数
 * 将两个数交换后，将原先小数位置后面的所有数字反转得到下一个字典序更大的排序
 */
public class nextPermutation31 {
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        if (n<=1) return;
        int i=n-2,j=n-1;
        for (; i >=0 ; i--,j--) {
            if (nums[i]<nums[j]){
                break;
            }
        }
        if (i>=0){
            int k=n-1;
            //说明不是最后一个排序
            while (k>=j&&nums[k]<=nums[i])
                k--;
            //找到这个需要交换的大数k
            swap(nums,i,k);
        }
        //反转j之后的元素
        reverse(nums,j);
    }
    void reverse(int[] nums,int start){
        int end=nums.length-1;
        while (start<end){
            swap(nums,start,end);
            start++;
            end--;
        }
    }
    void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
}
